A.1 Datasets Details of the datasets we introduce are presented in this section. Specific details about generation as well as statistics from the resulting datasets are delineated for each one below. A.1.1 Prefix sum data Binary string inputs of length nare generated by selecting a random integer in [0,2n)and expressing its binary representation with n digits. Datasets are produced by repeating this random process 10,000 times without replacement. Because the number of possible points increases exponentially as a function of n and the size of the generated dataset is fixed, it is important to note that the dataset becomes sparser in its ambient hypercube as nincreases.

A.1 Theoretical Proof The following is proof for Theorem 1 and 2 on Upper Bound on Lipschitz Constant of a DNN with Gaussian Distributed Weights, which is inspired by [67-69]. Let A be an (N n) matrix whose elements are independent standard normal random variables. Then, N n E[λmin(A)] E[λmax(A)] N+ n, where λmin and λmax denote the minimum and maximum singular values of A, respectively, and E[ ] represents the expected value. This can be extended to convolutional neural networks (CNN). Using doubly block circulant matrix the convolution operation can be represented by matrix multiplication.